package com.kaifamiao.N0810;

import org.w3c.dom.Node;

public class DoubleLinked {

    private Node head;

    private Node last;

    private int length;

    public boolean add(String value) {
        //创建一个节点，创建一个Node对象
        Node node = new Node(last, value);

        //链表中有元素吗
        if (head == null) {
            //链表没有元素
            head = node;
        } else {
            //把元素添加进去
            last.next = node;
        }

        //把添加的元素作为链表的最后一个元素
        last = node;
        length++;

        return true;
    }

    public String remove(int index) {
        checkIndex(index);
        //被删除的元素
        Node current = null;
        if (index == 0) {
            //被删除的元素
            current = head;

            head = head.next;
            head.prev = null;

            current.next = null;
        } else {
            //找被删除的元素
            current = head;
            for (int i = 1; i <= index; i++) {
                current = current.next;
            }
            if(index == length-1) {
                current = current.prev;
            }
            if(index <length-1) {
                //被删除元素的上一个元素
                Node prev = current.prev;
                //被删除元素的下一个元素
                Node next = current.next;
                //上一个元素的next指向下一个元素，下一个元素的prev指向上一个元素
                prev.next = next;
                next.prev = prev;
            }


            current.prev = null;
            current.next = null;
        }

        length--;
        return current.value;
    }

    public String set(int index, String value){
        checkIndex(index);
        Node current = head; // index = 0;
        for (int i = 1; i <= index; i ++){
            current = current.next;
        }
        String old = current.value;
        current.value = value;
        return old;
    }

    public boolean add(int index, String value){
        checkIndex0(index);
        Node current = new Node(value);

        if (index == 0){

            current = head.prev;
            head = current;

        } else if (index == length){
           // add(value);

        } else {
           Node prev = head;
           for (int i = 1; i < index; i++) {
               prev = prev.next;
           }
           Node add = prev.next;
           prev.next = current;
            current.next = current;

        }
        length ++;
        return true;
    }

    private void checkIndex0(int index){
        if (index < 0 || index > length){
            throw new NodeListIndexOutOfBoundsException("索引异常， index 应该是 0 到 " + length + "。但是接收到的是 " + index );
        }
    }

    public String get(int index){
        checkIndex(index);
        Node current = null;
        if (index < length / 2) {
            current = head; // index = 0;
            for (int i = 1; i <= index; i ++){
                current = current.next;
            }
        } else {
            current = last;
            for (int i = 0; i < (length - index - 1); i ++){
                current = current.prev;
            }
        }
        return current.value;
    }

    private void checkIndex(int index){
        if (index < 0 || index >= length){
            throw new NodeListIndexOutOfBoundsException("索引异常， index 应该是 0 到 " + (length - 1) + "。但是接收到的是 " + index );
        }
    }

    public int size(){
        return length;
    }


    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder("DoubleLinked { ");
        String str = "";
        if (head != null){
            Node current = head;
            while(current != null){
//                sb.append(current.value + ", ");
                sb.append(current + ", ");
                current = current.next;
            }
            str = sb.substring(0, sb.length() - 2);
        } else{
            str = sb.toString();
        }

        str += " }";
        return str;
    }

    private class Node {

        private Node prev;

        private String value;

        private Node next;

        public Node() {
        }

        public Node (String value){
            this.value = value;
        }

        public Node(Node prev,String value) {
            this.prev = prev;
            this.value = value;
        }

        public Node (Node prev,String value,Node next){
            this.prev = prev;
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return this.value;
        }
    }

    private class NodeListIndexOutOfBoundsException extends IndexOutOfBoundsException {
        public NodeListIndexOutOfBoundsException(String msg) {
            super(msg);
        }
    }
}